package src.dp.entire_bag;

import java.util.Arrays;

public class no279 {//用完全平方数凑n

    /**
     * 1. dp数组下标含义：和为 j 的完全平方数的最少数量为 dp[j], i*i 相当于物品，要凑的数 n 为背包容量
     * 2. 递推公式：dp[j] = Math.min(dp[j], dp[j - i*i] +1 )
     * 3. 初始化数组：因为每次取 min，所以要初始化为一个大的数 INT_MAX, dp[0]=0
     * 4. 遍历顺序：都可
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        //先物 后包，i*i 相当于物品，n 为背包容量
        for (int i = 1; i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                //注：这里不需要 if(dp[j - i*i] != Integer.MAX_VALUE)
                //因为有1的存在，任何一个数一定可以由1凑成，所以不会有"湊不成"的狀況发生，故不用判断
                dp[j] = Math.min( dp[j], dp[j - i * i] +1 );
            }
        }
        return dp[n];
    }
}
